1. Field of the Invention
The present invention relates to the field of microprocessor architecture. More specifically, the present invention relates to high performance processors such as digital signal processors that use very long instruction words (VLIW) or employ superscalar architectures.
2. Description of the Related Art
Two types of parallelism are commonly employed in microprocessor systems. In program level parallelism, more than one program is executed at the same time, normally on multiple processors. This form of parallelism is common, for example, in servers employing four to eight processors, all of which are connected to a single bus. Instruction level parallelism is another form of parallelism, in which a single instruction stream is executed on a single processor, but the instructions are dispatched to multiple functional units in the same cycle. This latter type of parallelism is used by Very Long Instruction Word (VLIW) and superscalar processors.
Program level parallelism includes task oriented parallelism and multithreading. In the simplest form of program level parallelism, different tasks are executed on different processors, so that the server handles more users, but no one user""s program can finish faster than it would if it had executed on a single processor system. In multithreading, a single program forks execution onto more than one processor, so that the program runs faster than it would on just one processor. Both forms of program level parallelism increase the net amount of useful work done in a given time interval. Task oriented parallelism allows the processor to perform parallel processing even when the individual programs are not specifically developed for parallel execution. Unfortunately, current VLIW machines are not well suited to any of these forms of program level parallelism.
VLIW architectures are rapidly gaining popularity and acceptance. The concept of VLIW is to fetch a very long instruction word, and to dispatch subinstructions contained in this very long word to a set of parallel functional units. For example, the very long instruction word might contain 256 bits, so that eight functional units each concurrently receive one 32-bit sub-instruction. In prior art systems, if all the sub-instruction words are not needed, the dispatcher can take multiple cycles to dispatch the instructions of the 256-bit instruction word to the functional units. One difference between VLIW machines and superscalar machines is that in VLIW machines the compiler schedules the instructions for parallel execution, so that the dispatch unit of a VLIW machine is very simple. In superscalar machines, the dispatch unit handles the parallel instruction scheduling using hardware algorithms, so that the dispatch unit of a superscalar machine is usually more complex.
One significant problem with VLIW machines is that, while they are capable of very high peak instruction per second counts, their performances may be much lower when executing actual programs. For example, consider the execution of a hypothetical VLIW processor having sixteen functional units. If the functional units are grouped into four sets of four cooperating functional units, with each group of functional units having primary access to a specific register file, then the system has four processing groups or has four sub-processors. These sub-processors all receive their instructions from the same instruction stream and follow the same control flow. That is, a branch taken in the program affects all four of the sub-processors in the system In many processing situations, the separate sub-processors may need to take different branches. However, there is only one instruction stream, so the various sub-processors executing various data sets must all execute in lock-step. One way this is handled is to make extensive use of conditionally executed instructions. Using conditional execution, there can be a single execution flow and only the sub-processors that need to execute instructions in a particular path do so, whereas the sub-processors that do not need to execute instructions sit idle. For example, assume four data streams are being processed in parallel on this hypothetical VLIW machine, and further assume that the code involves an IF-THEN-ELSE construct. At the machine level, a condition must be checked, and then a branch must be taken to either the THEN or the ELSE portions of the code. Since there are four data paths, it is very likely that among the four sub-processors, both the THEN and the ELSE program paths must be traversed. In the prior art, the processor executes both paths using conditionally executed instructions. In this way, each sub-processor performs useful operations on one path while effectively inserting xe2x80x9cno operationxe2x80x9d (NOP) instructions on the other. Since NOPs represent wasted cycles, performance is adversely affected.
Other problems arise when the various sub-processors work together on the same data. For example, if two data streams are to be processed on the same processor and the data involves complex numbers each having a real and an imaginary part, it would be advantageous for two processing groups to work together to deal with the real and imaginary parts of the complex data and to quickly compute the cross terms. This type of processing is quite common in communication systems processing and whenever a Fast Fourier Transform (FFT) is involved. In a hypothetical processor of sixteen functional units, eight functional units are available for each of two complex data streams. If all of the units are busy all the time, the peak number of instructions per cycle is achieved. In practice, however, it is very difficult to keep all functional units busy, and thus much lower efficiencies are achieved.
There are still other problems that create delays and inefficiencies. For example, if a branch is taken, multiple cycles need to be inserted while the pipelines empty and the new instruction flow makes its way through the pipeline. Other delays occur since the compiler must structure the code to avoid pipeline conflicts due to resource and data dependencies. These issues limit the amount of instruction-level parallelism that can be exploited in a program. That is, the local instruction level structure of the program very rarely allows a full set of instructions to be mapped onto the complete set of functional units in a given cycle.
Another problem with current VLIW architectures is the need to respond to interrupts. When interrupts occur, they can cause new programs to be fetched that will overwrite program words stored in the on-board cache, while creating their own sequence of cache misses. Cache misses are very expensive in VLIW machines. In the hypothetical processor having 16 functional units, the cache line fill involves sixteen slower external memory accesses per instruction, instead of a single on-chip cache-hit fetch cycle.
In short, while VLIW processors can theoretically achieve very high peak processing speeds, it is very difficult in practice to achieve these peak speeds on actual programs. This difficulty is compounded by inefficient branching, by conditionally executed instructions, and by difficulties arising from the need to perform multitasking and to respond efficiently to interrupts.
One aspect of the present invention is an enhanced VLIW architecture capable of alleviating the aforementioned shortcomings in the prior art. Another aspect of the present invention is a VLIW processor capable of executing multiple programs concurrently, allowing one program to execute in a cycle steal mode to make use of inefficiencies in another program. Yet another aspect of the present invention is a system to allow interrupts that can be processed with minimal cost in terms of clock cycles. The present invention further allows programs to fork execution down a plurality of branch paths in an efficient manner so that few cycles are wasted. The present invention provides a functional unit, a control unit, a dispatch unit, and cache structures. The present invention also provides methods that greatly increase the actual throughput that can be achieved on a VLIW architecture to thereby provide an actual performance that is much closer to peak performance than in current systems.
One aspect of the present invention is a multi-issue processor having a plurality of functional units responsive to processor instructions. The functional units have access to a primary register file. The processor comprises one or more auxiliary register files configured such that each of the functional units has access to a primary register file and to an auxiliary register file. The functional units are responsive to a register file selection signal. A dispatch unit is configured to accept instructions from a plurality of instruction streams and to generate the register file selection signal on an instruction-by-instruction basis to control whether each of the functional units uses the primary register file or the auxiliary register file. Preferably, the functional units further comprise one or more primary internal registers, one or more auxiliary internal registers, and an execution controller configured to accept a control signal from the dispatch unit. The execution controller is configured to control whether specified functional units use the primary register file or the second register file on a cycle-by-cycle basis. Also preferably, at least one of the instruction streams may come from a direct memory access controlled prefetch channel which is processed in the background in a cycle-steal mode. Also preferably, at least one of the instruction streams is activated in response to an interrupt. Also preferably, the instruction streams may be assigned different execution priorities under program control. The processor preferably also comprises a register renaming unit operative to rename registers and to accept inputs from and to retire results to either the primary register file or the auxiliary register file to support superscalar instruction dispatching and execution from a plurality of program sources. Preferably, the dispatch unit dispatches a plurality of instructions to a plurality of functional units in a single clock cycle. The dispatch unit selectively dispatches a first group of instructions from a first instruction stream to a first subset of functional units, and the dispatch unit selectively dispatches a second group of instructions from a second instruction stream to a second subset of functional units. The first and second instruction streams preferably comprise VLIW fetch packets, wherein each VLIW fetch packet comprises one or more execute packets, and wherein each execute packet comprises one or more instructions to be dispatched to one or more functional units in a single clock cycle.
Another aspect of the present invention is a processor having multiple functional units. Each functional unit has a plurality of pipeline stages. Each pipeline stage has access to a primary register file. The processor comprises one or more secondary register files, so that each of the functional units has access to a selection of register files. The selection of register files comprises a primary register file and a secondary register file. The functional units are responsive to a register selection signal to select a primary register file or a secondary register file. A plurality of pipelined register sets are included in each of the functional units. A dispatch unit accepts instructions from a plurality of instruction streams and sends instructions from the multiple instruction streams to the functional units. The dispatch unit asserts the register selection signal to select a register file from a set of register files. The set of register files comprises the primary register file and the secondary register file. The dispatch unit further generates a pipeline command for each of the functional units. The pipeline command selects one or more of the pipelined register sets in each of the functional units. A pipeline command delay line propagates the pipeline command so that, during each clock cycle, each stage of each functional unit is associated with a selected one of the instruction streams. Preferably, the plurality of instruction streams includes a first instruction stream and a second instruction stream, wherein the first and second instruction streams each comprises VLIW fetch packets. Each VLIW fetch packet comprises one or more execute packets, and each said execute packet comprises one or more instructions to be dispatched to one or more functional units in a single clock cycle. Preferably, in a given cycle, the dispatch unit is operative to dispatch all instructions from the next execute packet found in said the instruction stream and to dispatch one or more instructions from the current or next execute packet found in the second instruction stream, such that one execute packet is dispatched per cycle in the first instruction stream and such that execute packets in the second instruction stream are dispatched on a cycle-steal basis. In some cases, the execute packets in the second instruction stream are dispatched in multiple cycles.
Another aspect of the present invention is a processor which has multiple functional units. Each functional unit has one or more pipeline stages, and each pipeline stage has access to a primary register file. The processor comprises one or more secondary register files. Each of the functional units has access to a selection of register files comprising a primary register file and a secondary register file. Each functional unit is responsive to a register selection signal to select a primary register file or a secondary register file. The processor further includes one or more pipelined register sets in each of the functional units. A dispatch unit accepts instructions from a plurality of instruction streams and sends instructions from the plurality of instruction streams to the functional units. The dispatch unit asserts the register selection signal to select a register file from a set of register files. The set of register files comprises the primary register file and the secondary register file. A pipeline command delay line propagates the register selection signal so that, during each clock cycle, each stage of each functional unit is associated with a selected one of the instruction streams. Preferably, the plurality of instruction streams includes a first instruction stream and a second instruction stream, wherein the first and second instruction streams each comprise VLIW fetch packets. Each VLIW fetch packet comprises one or more execute packets, and each execute packet comprises one or more instructions to be dispatched to one or more functional units in a single clock cycle. Also preferably, in a given cycle, the dispatch unit is operative to dispatch all instructions from the next execute packet found in the first instruction stream, and to dispatch one or more instructions from the current or next execute packet found in the second instruction stream, such that one execute packet is dispatched per cycle in the first instruction stream and such that execute packets in the second instruction stream are dispatched on a cycle-steal basis. Also preferably, execute packets in the second instruction stream are dispatched in multiple cycles.
Another aspect of the present invention is a method for multithreading a VLIW processor or a computer system incorporating a VLIW processor. The method comprises the step of prefetching into a plurality of prefetch buffers a plurality of VLIW fetch packets from a plurality of instruction streams including a first instruction stream and a second instruction stream. Each VLIW fetch packet comprises one or more execute packets, and each execute packet comprises one or more instructions to be dispatched to one or more functional units in a single clock cycle. The method includes the further steps of dispatching all instructions contained in the next execute packet found in the first instruction stream, such that one execute packet is dispatched per cycle in first instruction stream; and dispatching one or more instructions from the most recent execute packet found in the second instruction stream, such that the most recent execute packet is dispatched on a cycle-steal basis. Preferably, the most recent execute packet is dispatched in multiple cycles. In preferred embodiments, the method further comprises the step of dispatching with each instruction a pipeline command for each of the functional units, whereby the pipeline command selects a first register set to be coupled to the functional unit if the instruction is from the first instruction stream. The pipeline command selects a second register set to be coupled to the functional unit if the instruction is from the second instruction stream. The pipeline command is dispatched via a pipeline command delay line so that, during each clock cycle, each functional unit is associated with a selected one of the instruction streams.
Another aspect of the present invention is a method of multithreading in a superscalar processor or a computer system incorporating a superscalar processor. The method comprises the step of prefetching into a plurality of prefetch buffers a plurality of instruction fetch packets from a plurality of instruction streams. A first prefetch buffer is associated with a first instruction stream and a second prefetch buffer is associated with a second instruction stream. The method includes the step of determining which instructions in the first prefetch buffer are ready to dispatch in parallel in a given cycle. The method dispatches all instructions determined to be ready to dispatch from the first prefetch buffer for which hardware resources are available. The method determines which instructions in the second prefetch buffer are ready to dispatch in parallel in said given cycle. The method dispatches one or more instructions from the second prefetch buffer using the hardware resources not already in use by the instructions in the first prefetch buffer. Preferably, the method comprises the further step of dispatching with each instruction a pipeline command for each of the hardware resources, whereby the pipeline command selects a first register set to be coupled to a first hardware resource when the instruction is from the first instruction stream, and the pipeline command selects a second register set to be coupled to the first hardware resource when the instruction is from the second instruction stream. Preferably, the pipeline command is propagated by a pipeline command delay line so that, during each clock cycle, each hardware resource is associated with a selected one of the instruction streams.
Another aspect of the present invention is a method of multithreading in a superscalar processor or a computer system incorporating a superscalar processor. The method comprises the steps of: prefetching into a plurality of prefetch buffers a plurality of instruction fetch packets from a plurality of instruction streams including a first prefetch buffer associated with a first instruction stream and a second prefetch buffer associated with a second instruction stream; determining which instructions in the first and second prefetch buffers are ready to dispatch in parallel in a given cycle; and dispatching instructions determined to be ready to dispatch from the first and second prefetch buffers for which hardware resources are available based on a scheduling algorithm. Preferably, the scheduling algorithm is a round robin scheduling algorithm.
Another aspect of the present invention is a multi-issue processor having multiple functional units. Each functional unit has one or more pipeline stages with each pipeline stage having access to a primary resource. The processor comprises one or more secondary resources provided as a selection of resources accessible by selected functional units. A thread indicator signal designates from which instruction stream an instruction was dispatched,. The selected functional units are responsive to the thread indicator signal. A dispatch unit concurrently accepts multiple instructions from each of a plurality of instruction streams. In a given cycle, the dispatch unit selectively sends instructions from multiple instruction streams to the functional units. The dispatch unit asserts the thread indicator signal to select a set or resources to be accessed by the functional units responsive to the thread indicator signal while carrying out said instruction. A thread indicator delay line propagates the thread indicator signal so that, during each clock cycle, different stages of the functional units are responsive to the thread indicator signal to selectively use the selected set of resources.
Another aspect of the present invention is a method of operating an instruction cache in a processor where the instruction cache has a plurality of cache lines and a plurality of cache banks. The method comprises the steps of inserting data into each cache bank according to a cache bank selector field indicator; and using the cache bank selector field while filling each of the cache lines to ensure that instructions on parallel branch paths reside in different cache banks.
Another aspect of the present invention is a processor which has one or more functional units. Each of the functional units has access to a primary register file and is responsive to instructions emanating from a plurality of instruction streams. The processor comprises an instruction cache memory which is divided into one or more cache banks. A plurality of program counters and a plurality of prefetch registers are included in the processor. Each of the prefetch registers is configured to store a plurality of sub-instructions for the functional units. A multiple input dispatch unit is configured to accept input instructions from a plurality of instruction streams with ranked priority levels and to dispatch the input instructions to the functional units. The multiple input dispatch unit further provides each functional unit a code indicative of the instruction stream from which each input instruction was accepted, such that the functional units can process each instruction using a register set associated with the instruction stream.
Another aspect of the present invention is a method for executing a conditional branch construct on a VLIW processor with multiple sub-processors, where each sub-processor comprises a group of data registers and functional units. The method comprises the step of factoring the conditional branch construct into a plurality of execution paths such that an execution flow on the processor is disjoined into a plurality of execution paths. The method generates a sequence of VLIW instruction words for each path such that all of the sequences are aligned. Each of the sequences is padded with NOPs to maintain alignment if necessary. The method further includes the steps of maintaining a respective instruction pointer for each execution path; checking multiple conditions based on multiple data streams for each of the sub-processors; allocating each of the sequences to a sub-processor; fetching a single VLIW from two or more separate addresses in a cache concurrently using a mask field; and executing the sequences of VLIW instruction words. Preferably, the conditional branch construct is an IF-THEN-ELSE construct. Alternatively, the conditional branch construct is a CASE construct.
Another aspect of the present invention is a method for parallel execution of a plurality of execution paths on a VLIW processor with multiple sub-processors, where each sub-processor comprises a group of data registers and functional units. The method comprises the step of generating a sequence of VLIW instruction words for each execution path such that all of the sequences are aligned. Each of the sequences is padded with NOPs to maintain alignment if necessary. The method includes the further steps of maintaining a respective instruction pointer for each execution path; checking multiple conditions based on multiple data streams for each of the sub-processors; allocating each of the sequences to a sub-processor; fetching a single VLIW from two separate addresses in a cache concurrently using a mask field; and executing the sequences of VLIW instruction words.
Another aspect of the present invention is a method for parallel execution of a plurality of execution paths on a VLIW processor with multiple sub-processors, where each sub-processor comprises a group of data registers and functional units. The method comprises the step of generating a sequence of VLIW instruction words for each execution path such that all of the sequences are aligned. Each of the sequences is padded with NOPs to maintain alignment if necessary. The method includes the further steps of maintaining a respective instruction pointer for each execution path; checking multiple conditions based on multiple data streams for each of the sub-processors; allocating each of the sequences to a sub-processor; fetching a single VLIW from two separate addresses in a cache concurrently using a mask field; and executing the sequences of VLIW instruction words.
Another aspect of the present invention is a processor having one or more functional units responsive to processor instructions. The functional units have access to a primary register file. The processor comprises one or more auxiliary register files configured such that each of the functional units has access to a primary register file and to an auxiliary register file; and a register file selector for each of the functional units. The register file selector accepts instructions from a plurality of instruction streams and selects a register file for each of the functional units on an instruction-by-instruction basis. Preferably, the functional units further comprise a plurality of pipelines; and a pipeline selector which selects a pipeline for each functional unit. The pipeline is selected from the plurality of pipelines on a cycle-by-cycle basis.
Another aspect of the present invention is a processor which comprises one or more functional units; a program cache which provides a primary execution stream of instructions to a first prefetch buffer for use by the one or more functional units; a second prefetch buffer which provides a secondary execution stream of instructions to the one or more functional units in response to an interrupt applied to the one or more functional units; and a DMA controller which fetches the secondary stream of instructions and stores the secondary stream of instructions in the prefetch second buffer. Preferably, the primary instruction stream comprises VLIW instructions, and the program cache is a VLIW program cache. Also preferably, the second instruction stream is accessed in response to an interrupt.
Another aspect of the present invention is a pipelined processor which multiplexes the processing of a first instruction stream and a second instruction stream on a cycle-by-cycle basis, wherein the first instruction stream and the second instruction stream are both fetched into respective prefetch buffers from a single program cache. Instructions from the second instruction stream are fetched from the program cache during intervals when a pipeline operation related to the processing of the first instruction stream would normally stall the fetching of instructions from the program cache. Preferably, the instructions are VLIW instructions, and the program cache is a VLIW program cache.
Another aspect of the present invention is a method for operating a pipelined processor which multiplexes the processing of a first instruction stream and a second instruction stream on a cycle-by-cycle basis. The method comprises the steps of fetching instructions for a first instruction stream from a program cache into a first prefetch buffer; and fetching instructions for a second instruction stream from memory into a second prefetch buffer under control of a direct memory access controller.
Another aspect of the present invention is a very long instruction word (VLIW) processor which exploits program level parallelism as well as instruction level parallelism. Unlike prior VLIW machines which obtain speed advantages using instruction level parallelism, the present processor exploits the parallelism inherent in a VLIW processor by providing new instruction level mechanisms to separate processor execution into parallel threads. This separation allows greater hardware use because more than one program can exploit instruction level parallelism on the system at the same time. A first program and a second program execute concurrently such that the second program executes using resources and cycles that would have been wasted by the first program. This construct is especially useful where the second program is an interrupt service routine because the interrupt service routine can be threaded through the machine with high or low priority while the functional units still process the first program stream. A superscalar version of the processor is also described.